package 极客算法训练营.chapter03;

public class K个一组翻转链表 {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);
        ListNode node8 = new ListNode(8);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;
//        ListNode node = reverseKGroup(node1, 3);
        ListNode node = reverseList(node1, 4);
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }

//    private ListNode[] indexs = null;

    public static ListNode reverseKGroup(ListNode head, int k) {
        int count = 0;
        ListNode newNode = new ListNode(0);
        newNode.next = head;
        while (head != null) {
            count++;
            head = head.next;
        }
        if (count < k) return newNode.next;
        int num = count / k;
        ListNode tmp = newNode;
        for (int i = 0; i < num; i++) {
            tmp = reverseList(tmp, k);
        }
        return newNode.next;
    }

    public static ListNode reverseList(ListNode _head, int k) {
        ListNode[] indexs = new ListNode[k + 1];
        indexs[0] = _head;
        for (int i = 1; i <= k; i++) {
            indexs[i] = indexs[i - 1].next;
        }
        ListNode newStart = indexs[k].next;
        indexs[0].next = indexs[k];
        for (int i = k; i > 1; i--) {
            indexs[i].next = indexs[i - 1];
        }
        indexs[1].next = newStart;
        return indexs[1];
    }
}
